package top.ivansong92.example.leetcode.learning.other;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

/**
 * 贪心案例
 */
public class GreedyExamp {

    @Test
    public void testCanJump() {
        System.out.println(canJump(new int[]{3,2,1,1,4}));
    }

    /**
     * 55. 跳跃游戏
     * @param nums
     * @return
     */
    public boolean canJump(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return true;
        }
        int mostStep = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > mostStep) {
                break;
            }
            mostStep = Math.max(mostStep, i + nums[i]);
            if (mostStep >= nums.length - 1) {
                return true;
            }
        }
        return false;
    }


    /**
     * 45. 跳跃游戏 II
     * @param nums
     * @return
     */
    public int jump(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return 0;
        }

        int mostStep = 0;
        Integer[] step = new Integer[nums.length];
        step[0] = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > mostStep) {
                break;
            }

            if (nums[i] == 0) {
                continue;
            }
            mostStep = Math.max(mostStep, i + nums[i]);
            if (mostStep >= nums.length - 1) {
                return step[i] + 1;
            }

            for (int j = i + 1; j < (i + nums[i]); j++) {
                if (step[j] == null) {
                    step[j] = (step[i] != null ? step[i] + 1 : 1);
                    continue;
                }
                step[j] = Math.min(step[j], step[i] + 1);
            }
        }
        return 0;
    }
    public int jumpV2(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return 0;
        }

        return 0;
    }

    /**
     * 1654. 到家的最少跳跃次数
     * @param forbidden
     * @param a
     * @param b
     * @param x
     * @return
     */

    public int minimumJumps(int[] forbidden, int a, int b, int x) {
        Set<Integer> filter = Arrays.stream(forbidden).boxed().collect(Collectors.toSet());
        int step = 0, index = 0;
        while (true) {
            if (filter.contains(index)) {
                return -1;
            }

            if (index < x) {
                index += a;
                step ++;
            } else if (index == x) {
                return step;
            } else {
                index += b;
                step ++;
            }
        }
    }
}
